package top.dprkshow.practice.heap;

/**
 * @author Kent HAN
 * @date 2021/8/27
 */
public class Heap {
    static int size = 0, capacity = 1000;
    static int[] nodes = new int[1001];

    static void insert(int value) {
        size++;
        nodes[size] = value;
        siftUp(size);
    }

    static int getMax() {
        return nodes[1];
    }

    static int getSize() {
        return size;
    }

    static boolean isEmpty() {
        return size == 0;
    }

    static int extractMax() {
        int maxValue = getMax();
        removeNode(1);
        return maxValue;
    }

    static void removeNode(int index) {
        nodes[index] = nodes[size];
        size--;
        siftDown(index);
    }

    static void siftUp(int index) {
        while (index > 1) {
            if (nodes[index] > nodes[index / 2]) {
                swap(index, index / 2);
            } else {
                break;
            }
            index /= 2;
        }
    }

    static void siftDown(int index) {
        int swapIndex = 0, left = index * 2, right = index * 2 + 1;
        if (left <= size && nodes[left] > nodes[index]) {
            swapIndex = left;
        }
        if (right <= size && nodes[right] > nodes[swapIndex]) {
            swapIndex = right;
        }
        if (swapIndex != 0) {
            swap(index, swapIndex);
            siftDown(swapIndex);
        }
    }

    static void heapify(int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            siftDownV2(arr, i);
        }
    }

    static void siftDownV2(int[] arr, int index) {
        int swapIndex = -1, left = index * 2 + 1, right = index * 2 + 2;
        if (left < arr.length && arr[left] > arr[index]) {
            swapIndex = left;
        }
        if (right < arr.length && arr[right] > arr[swapIndex]) {
            swapIndex = right;
        }
        if (swapIndex != -1) {
            int tmp = arr[index];
            arr[index] = arr[swapIndex];
            arr[swapIndex] = tmp;
            siftDownV2(arr, swapIndex);
        }
    }

    static void swap(int indexA, int indexB) {
        int tmp = nodes[indexA];
        nodes[indexA] = nodes[indexB];
        nodes[indexB] = tmp;
    }

    static void printData() {
        for (int i = 1; i <= size; i++) {
            System.out.print(nodes[i] + " | ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
//        insert(100);
//        insert(200);
//        insert(300);
//        insert(150);
//        insert(230);
//        insert(410);
//
//        int maxValue = extractMax();
//        System.out.println(maxValue);
//
//        printData();
//
//        System.out.println(getMax());
//        System.out.println(getSize());
//        System.out.println(isEmpty());

        int[] arr = new int[]{0,1,2,3,4,5,6,7,8};
        heapify(arr);

    }
}
